This invention proposes a novel nonlinear filter called adaptive weighted fuzzy mean (AWFM) filter which is capable of removing high density Gaussian impulse noises in polluted images.
Conventionally, nature of input signal is essential when one is designing non-adaptive non-time-variant filters. However, uncertainty exists because one is unable to obtain desired information about input signal or because input signal is time-variant. In order to overcome this uncertainty problem, adaptive algorithm has been proposed by many researchers such as A. C. Tan etc. in IEEE Trans. Circuits Syst. II Vol. 44 (5) p358-370 (1997). Among the proposed adaptive algorithms such as that proposed by Petrus C. W. etc. in 1996 U.S. Pat. No. 5,581,494, recurrent methods of either Least Mean Square Error or Least Mean Absolute Error are introduced for parameter adjustments. But when the desired signal is unable to obtain or is uncertain in nature, reasonable results can""t be possible by the methods above. In addition, repeating recurrent estimations can slow down the filter, which is not appropriate for high speed filtering. In view of hardware fabrication, complex circuits are required by recurrent estimations, either Least Mean Square Error or Least Mean Absolute Error, in order to manage data storage and the recurrent process. By current technology, it""s still not feasible to achieve filtering with small circuits and high speed operation. Hence, the present invention proposes a direct method for adaptive filtering as well as a corresponding method of hardware synthesis in order to achieve the objectives. The adaptive, filter proposed in the present invention is highly stable and can quickly as well as effectively restore the polluted image without recurring estimations. The image can be recovered no matter how high the S/N level is. In addition, the filter in the present invention is input-dependent and time-variant in nature so that parameters can be weighted according to the input signal and there is no need to acquire nature of the input.
Recently fuzzy set theory, such as by X. J. Zeng in IEEE Trans. Fuzzy Systems Vol. 3 (2) p219-235 (1995), has been successfully applied on the estimations for non-linear systems or systems with uncertainty. The theory has the advantages of small memory requirement, short adapting time, and easy fabrication. Base on the theory of fuzzy logics, the present invention proposes a AWFM filter which can adapt itself according to a number of fuzzy rules. The AWFM filter can be treated as the extension of the WFM filter reported by C. S. Lee in Int. J. Fuzzy Sets and Systems Vol. 89 (2) 157-180 (1997). These fuzzy rules can be obtained by a simple algorithm without recurrent adaptations. FIG. 1 shows block diagrams of the AWFM filter. When the input signal x(i, j) reaches WFM, a set of fuzzy rule in the knowledge base is carried out to adjust weights of the WFM. The output of WFM, ywfm(i, j), is then sent to another set of fuzzy rules for quality evaluation and weight adjustment so that the fuzzy detector can detect the noise level "xgr"(i, j). Final output of the AWFM is determined by the, dynamic seletor among "xgr"(i, j), ywfm(i, j), ywfm(i, j)+"xgr"(i, j), and ywfm(i, j)xe2x88x92"xgr"(i, j).
In the hardware aspect, there are two major conventional categories for the synthesis of filters: (1) the analog data sampling technique by B. S. Song in IEEE J. of Solid-State Circuits Vol. 24 p.320-324 (1989), or ROC Patent Announcement No.135264 and 217475; (2) the continuous-time technique by J. Silva-Martinez in IEEE J. of Solid-State Circuits p993-1001 (1993), ROC Patent Announcement No.182719, 159301, and 143145. The former has higher accuracy in low noise applications while the latter can be applied for high frequency application. However, conventional filters are linear in nature without input-dependent or time-variant considerations. The present invention proposes a hardware synthesis method which introduces generic LR fuzzy cells adopted CMOS current mode, reported by the inventors in IEEE Trans. on Fuzzy Systems Vol. 6 (2) p266-285 (1998). The generic LR fuzzy cells are well proven for high speed fuzzy logic estimations and show good CMOS noise immunity. Many types of fuzzy rules can be represented by connecting these generic cells such as gates in conventional digital systems.
In general, a WFM filter is a mean filter based on fuzzy number calculations. Conventional mean filters can""t remove highly polluted impulse noises while WFM filters can, well and easily. Considering a clean image S with L gray levels, the gray value for each pixel lies between 0 and Lxe2x88x921 so that the gray scale pollution for the pixels in S can be represented by a fuzzy subset [0, Lxe2x88x921]. Each fuzzy subset represents an abstract concept (i.e. brightness) for the gray value, for example, dark (DK), median (MD), or bright (BR). Membership functions of these fuzzy subsets decide how each pixel relates to a specific abstract concept. The fuzzy subset can be obtained from the gray scale histogram according to C. S. Lee in Int. J. Fuzzy Sets and Systems vol. 89 (2) p157-180 (1997), or given by a specialist in the field. When transferring to the input of a image processing system, image S may be polluted so a filter is necessary for removing noises. Let X=[x(i, j)]N1xc3x97N2 and Y=[yWFM(i, j)]NN1xc3x97N2 represent the original image and the WFM filtered image respectively, pixel x(i, j) in X could be polluted by noise so that the gray value changes to x(i, j)=s(i, j)+n(i, j). It is the WFM filter""s job to estimate s(i, j) with filtered signal yWFM (i, j) by the fuzzy subsets.
According to H. J. Zimmermann in Fuzzy set theory and its applications, the fuzzy sets used in WFM filters are L-R type, which can be represent by                                           μ            M                    ⁡                      (            x            )                          =                  {                                                                                                                L                      ⁡                                              (                                                                                                            m                              M                                                        -                            x                                                                                α                            M                                                                          )                                                              ,                                    ⁢                                      xe2x80x83                                                                                                                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ≤                                      m                    M                                                                                                                                                                  R                      ⁡                                              (                                                                              x                            -                                                          m                              M                                                                                                            β                            M                                                                          )                                                              ,                                    ⁢                                      xe2x80x83                                                                                                                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                     greater than                                       m                    M                                                                                                          (        1        )            
where L(y)=R(y)=LR(y)=max(0, 1xe2x88x92y) for any real. In other words L and R equal to LR. xcexcM(x) can be represented by [mM, xcex1M, xcex2M]LR. Let WFM(xc2x7) represent the function of WFM filters, the (i, j)th filtered pixel can be expressed by
yWFM(i, j)=WFM(Xaxc3x97b(i, j))xe2x80x83xe2x80x83(2)
where                                                         X              _                                      3              xc3x97              3                                ⁡                      (                          i              ,              j                        )                          =                  [                      xe2x80x83                    ⁢                                                                      x                  ⁡                                      (                                                                  i                        -                        1                                            ,                                              j                        -                        1                                                              )                                                                                                x                  ⁡                                      (                                                                  i                        -                        1                                            ,                      j                                        )                                                                                                x                  ⁡                                      (                                                                  i                        -                        1                                            ,                                              j                        +                        1                                                              )                                                                                                                        x                  ⁡                                      (                                          i                      ,                                              j                        -                        1                                                              )                                                                                                x                  ⁡                                      (                                          i                      ,                      j                                        )                                                                                                x                  ⁡                                      (                                          i                      ,                                              j                        +                        1                                                              )                                                                                                                        x                  ⁡                                      (                                                                  i                        +                        1                                            ,                                              j                        -                        1                                                              )                                                                                                x                  ⁡                                      (                                                                  i                        +                        1                                            ,                      j                                        )                                                                                                x                  ⁡                                      (                                                                  i                        +                        1                                            ,                                              j                        +                        1                                                              )                                                                                ⁢                      xe2x80x83                    ]                                    (        3        )            
Functions of WFM filters can be described by a set of fuzzy rules defined as followed:
Fuzzy rules for WFM filters can be generally expressed by:
If U is M then V is fM(U)
where M is a fuzzy set expressed by [mM, xcex1M, xcex2M]LR, both U and V are matrix [u(i, j)]axb and [v(i, j)]axb (in WFM, a=b=3), so the subject xe2x80x9cU is Mxe2x80x9d and xe2x80x9cV is fM (U)xe2x80x9d mean [u(i, j) is M]axb and [v(i, j) is fM(U)]axb. So the result fuzzy set fM(U) is defined by:
fM(U)={(xcexcM(u(i, j)),u(i, j))|∀u(i, j)xcex5U}
where xcexcM(u(i, j)) coresponses to input u(i, j) on the assumption that u(i, j) is the matching degree of M.
The fuzzification formula is as follow:                     v        =                                            ∑                              i                =                1                            a                        ⁢                                          ∑                                  j                  =                  1                                b                            ⁢                                                                    μ                    M                                    ⁡                                      (                                          u                      ⁡                                              (                                                  i                          ,                          j                                                )                                                              )                                                  xc3x97                                  u                  ⁡                                      (                                          i                      ,                      j                                        )                                                                                                          ∑                              i                =                1                            a                        ⁢                                          ∑                                  j                  =                  1                                b                            ⁢                                                μ                  M                                ⁡                                  (                                      u                    ⁡                                          (                                              i                        ,                        j                                            )                                                        )                                                                                        (        4        )            
To filt a pixel, a WFM filter first constructs three fuzzy rules for three different fuzzy mean procedures:
Rule 1: If X is DK then YDK is fDK(X)
Rule 2: If X is MD then YMD is fMD(X)
Rule 3: If X is BR then YBR is fBR(X)
xe2x80x83where DK represents the fuzzy set for xe2x80x9cdarkxe2x80x9d, MD for xe2x80x9cmediumxe2x80x9d, BR for xe2x80x9cbrightxe2x80x9d. These fuzzy rules will generate three crisp values yDK, yMD, and yBR after defuzzification. Beside the three fuzzy mean procedures, WFM filters also carries out a fuzzy estimation defined by Rule 4.
H. J. Zimmermann has reported a LR type of fuzzy interval I (see Fuzzy set theory and its applications) in 1991, where membership functions of I are constructed by two functions L and R, and four parameters: (mIl, mIr) xcex5R2∪{xe2x88x92∞, ∞}, xcex11 and xcex21. The fuzzy interval I=[mIl,mIr,xcex11,xcex21]LR can be expressed by                                           μ            l                    ⁡                      (            x            )                          =                  {                                                                                          L                    ⁡                                          (                                                                                                    m                            ll                                                    -                          x                                                                          α                          l                                                                    )                                                        ,                                                                                                  for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ≤                                      m                    ll                                                                                                                        1                  ,                                                                                                  for                    ⁢                                          xe2x80x83                                        ⁢                                          m                      ll                                                        ≤                  x                  ≤                                      m                    lr                                                                                                                                            R                    ⁡                                          (                                                                        x                          -                                                      m                            lr                                                                                                    β                          l                                                                    )                                                        ,                                                                                                  for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ≥                                      m                    lr                                                                                                          (        5        )            
According to C. S. Lee etc. in Int. J. Fuzzy Sets and Systems Vol. 89 (2) p157-180, (1997), ES which is described by the fuzzy estimator of WFM filters can be accomplished by the following fuzzy rule,
Rule 4: If X is I then the fuzzy estimate ES of X is f1(X)
xe2x80x83where X is a sampling matrix based on x(i, j), I is the fuzzy interval obtained by histogram. Defuzzification es(X) for Rule 4 can be obtained according to equation (4).
Finally, Rule 5 represents a decision procedure, which selects one output among that of Rule 1 through 3 as the final output for WFM filters:
Rule 5: IF Yt is closest_to_ES then yWFM is fclosestxe2x80x94toxe2x80x94ES (Yt)
xe2x80x83where vector Yt=(yDK, yMD, yBR) and fuzzy set closest_to_ES which defined in [0, Lxe2x88x921] can be described by the following membership function:                                           μ                          closest_to              ⁢              _ES                                ⁡                      (            u            )                          =                  {                                                                                          1                    ,                                    ⁢                                      xe2x80x83                                                                                                                                          if                      ⁢                                              xe2x80x83                                            ⁢                      u                                        =                                          arg                      ⁢                                              xe2x80x83                                            [                                                                        min                                                                                    y                              t                                                        ∈                                                                                          Y                                t                                                            _                                                                                                      ⁢                                                  (                                                      "LeftBracketingBar"                                                                                          y                                t                                                            -                              es                                                        "RightBracketingBar"                                                    )                                                                    ]                                                        ,                                                                                                      0                  ,                                                                              otherwise                  .                                                                                        (        6        )            